class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution:

    def createTree(self, nums: list):
        def level(index):
            if index >= len(nums) or nums[index] is None:
                return None
            root = TreeNode(nums[index])
            root.left = level(2 * index + 1)
            root.right = level(2 * index + 2)
            return root
        return level(0)

    def preorderOut(self, root: TreeNode) -> list:
        def preorder(root):
            if root:
                res.append(root.val)
                preorder(root.left)
                preorder(root.right)
        res = []
        preorder(root)
        return res

    def inorderOut(self, root: TreeNode) -> list:
        def preorder(root):
            if root:
                preorder(root.left)
                res.append(root.val)
                preorder(root.right)
        res = []
        preorder(root)
        return res

    def postorderOut(self, root: TreeNode) -> list:
        def postorder(root):
            if root:
                postorder(root.left)
                postorder(root.right)
                res.append(root.val)
        res = []
        postorder(root)
        return res

# 前序：[3, 9, 20, 15, 7] 
# 中序：[9, 3, 15, 20, 7]
    def buildTree(self, preorder: list, inorder: list) -> TreeNode:
        def build(preorder, inorder, p1, p2, i1, i2):
            if p1 > p2 or i1 > i1:
                return None
            root_val = preorder[p1]
            # 找到根节点在中序排列中对应的位置
            pos = indexs[root_val]
            root = TreeNode(val=root_val)
            # 遍历左子树
            root.left = None if pos == i1 else build(preorder, inorder, p1+1, p1 + (pos - i1), i1, pos - 1)
            # 遍历右子树
            root.right = None if pos == i2 else build(preorder, inorder, p1 + (pos - i1) + 1, p2, pos + 1, i2)
            return root
        indexs = {}
        n = len(inorder)
        for i in range(n):
            indexs[inorder[i]] = i
        return build(preorder, inorder, 0, n-1, 0, n-1)
    
      #  0  1 2  3   4   5   6
# 中序：[1, 9, 2, 3, 15, 20, 7]
# 后序：[1, 2, 9, 8, 15, 7, 20]
    def buildTree2(self, inorder: list, postorder: list) -> TreeNode:
        def build(inorder, postorder, i1, i2, p1, p2):
            if p1 > p2 or i1 > i2:
                return None
            root_val = postorder[p2]
            pos = indexs[root_val]
            root = TreeNode(val=root_val)
            root.left = None if pos == i1 else build(inorder, postorder, i1, pos-1, p1, p1 - i1 + pos - 1)
            root.right = None if pos == i2 else build(inorder, postorder, pos + 1, i2, p1 - i1 + pos, p2 - 1)
            return root
        n = len(inorder)
        indexs = {}
        for i in range(n):
            indexs[inorder[i]] = i
        mget = build(inorder, postorder, 0, n-1, 0, n-1)
        return mget

        
# 前序：[3, 9, 20, 15, 7] 
# 中序：[9, 3, 15, 20, 7]
#     3
#     /\
#    9  20
#   /\   /\
#  1 2  15 7
# 解题思路: 
# 先遍历前序节点，对于前序的根节点，在中序节点[i1, i2]中找到根节点的位置pos,
# 就可以将中序节点分成：左子树[i1, pos-1]、右子树[pos+1, i2]
# 通过左右子树的区间，可以计算出左右子树节点的个数，假设为m, n。
# 然后在前序节点中，从根节点往后的m个节点为左子树, 再往后n个节点为右子树

# 中序：[9, 3, 15, 20, 7]
# 后序：[9, 15, 7, 20, 3]
# 解题
# 先遍历后序节点


s = Solution()
# print(s.postorderOut(s.createTree([3, 9, 20, 1, 2, 15, 7])))
tree = [1, 2, 3, 4, 5, 6, 7]
preorder = s.preorderOut(s.createTree(tree))
inorder = s.inorderOut(s.createTree(tree))
postorder = s.postorderOut(s.createTree(tree))
print('前序：', preorder)
print('中序：', inorder)
print('后序：', postorder)
res = s.buildTree(preorder, inorder)
print('前序: ', s.preorderOut(res))

res = s.buildTree2(inorder, postorder)
print('前序: ', s.preorderOut(res))


# res = s.buildTree2([1, 9, 2, 3, 15, 20, 7], [1, 2, 9, 15, 7, 20, 3])
# print(s.preorderOut(res))
# print(s.inorderOut(res))
# print(s.postorderOut(res))
# print(res)
